home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / std / c / 443 < prev    next >
Encoding:
Internet Message Format  |  1996-08-06  |  1.7 KB
  1. Path: solon.com!not-for-mail
  2. From: schwarz@a3.complang.tuwien.ac.at (Konrad Schwarz)
  3. Newsgroups: comp.lang.c.moderated,comp.lang.c,comp.std.c
  4. Subject: Re: HELP IN WRITING MY FIRST PROGRAM ASSINGMENT
  5. Date: 26 Feb 1996 07:07:01 -0600
  6. Organization: TU Wien
  7. Sender: clc@solutions.solon.com
  8. Approved: clc@solutions.solon.com
  9. Message-ID: <4gsb9l$46a@solutions.solon.com>
  10. References: <3127FF7A.6442C3B8@eden.com> <4gfhkj$3p8@solutions.solon.com> <4ggbi9$83k@solutions.solon.com> <4ghnnc$dj9@solutions.solon.com> <4ghoam$dp4@solutions.solon.com>
  11. NNTP-Posting-Host: solutions.solon.com
  12.  
  13. In article <4ghoam$dp4@solutions.solon.com>, seebs@solutions.solon.com (Peter Seebach) writes:
  14.  
  15.     [qsort problem]
  16.  
  17. |> To clarify: I believe it is incorrect for the library to do so; although
  18. |> it's pretty tenuous, the "which is called with two arguments that point to
  19. |> the objects being compared" seems to mean that to me.  My rationale is that
  20. |> the compiler *cannot* prove that the objects do not depend on being parts
  21. |> of a larger array.  For instance, consider an array of 200 objects; sort
  22. |> the first 100, with a comparison routine that compares not only the objects,
  23. |> but the objects 100 further in the "real" array.  I believe this to be
  24. |> conforming.
  25.  
  26. The qsort routine rearranges the array passed to it.  I don't think it
  27. is possible for the comparision function to sort the real array 100 objects
  28. further on in lockstep with the qsort routine, without relying on the
  29. algorithm of qsort---which is implementation defined.  In this
  30. case, the comparision function is not well-defined, since at some call,
  31. a < b, later, a > b.
  32.  
  33. By the way, what is the relation of the ``quicker sort algorithm'' mentioned
  34. in many manuals to the classic quick sort algorithm?  Is it best-of-three?
  35.  
  36. Konrad Schwarz
  37.